#include <iostream>
#include "IntroAlgorithm.h"
using namespace std;

void InsertionSort(vector<int> &array) {
	for (int i = 1; i < array.size(); ++i) {
		int temp = array[i];
		int j = i - 1;
		while (j >= 0 && array[j] > temp) {
			array[j + 1] = array[j];
			--j;
		}
		array[j + 1] = temp;
	}
}

void SelectionSort(vector<int> &array) {
	for (int i = 0; i < array.size() - 1; ++i) {
		int pos = i;
		for (int j = i + 1; j < array.size(); ++j)
			if (array[j] < array[pos])
				pos = j;
		swap(array[pos], array[i]);
	}
}

void BubbleSort(vector<int> &array) {
	for (int i = 1; i < array.size(); ++i) {
		for (int j = 0; j < array.size() - i; ++j) {
			if (array[j] > array[j + 1])
				swap(array[j], array[j + 1]);
		}
	}
}

void MergeSortBody(vector<int> &array, int begin, int end);
void MergeSort(vector<int> &array) {
	MergeSortBody(array, 0, array.size() - 1);
}

void Merge(vector<int> &array, int begin, int mid, int end);
void MergeSortBody(vector<int> &array, int begin, int end) {
	if (begin == end) 
		return;

	int mid = (begin + end) / 2;
	MergeSortBody(array, begin, mid);
	MergeSortBody(array, mid + 1, end);
	Merge(array, begin, mid, end);
	
#if 0
	cout<<endl;
	copy(array.begin(), array.end(), ostream_iterator<int>(cout, " "));
	cout<<endl;
#endif
}

void Merge(vector<int> &array, int begin, int mid, int end) {
	int begin1 = begin, end1 = mid, begin2 = mid + 1, end2 = end;
	vector<int> temp;

	while (begin1 <= end1 && begin2 <= end2) {
		if (array[begin1] < array[begin2]) {
			temp.push_back(array[begin1]);
			++begin1;
		} else {
			temp.push_back(array[begin2]);
			++begin2;
		}
	}

#if 0
	cout<<endl;
	copy(temp.begin(), temp.end(), ostream_iterator<int>(cout, " "));
	cout<<endl;
#endif

	if (begin1 > end1) {
		copy(array.begin() + begin2, array.begin() + end2 + 1, back_inserter(temp));
	} else {
		copy(array.begin() + begin1, array.begin() + end1 + 1, back_inserter(temp));
	}

	copy(temp.begin(), temp.end(), array.begin() + begin);
}

template<class T>
void QuickSortBody(vector<T> &array, int begin, int end);
template<class T>
void QuickSort(vector<T> &array) {
	QuickSortBody<T>(array, 0, array.size() - 1);
}

//stupid C++ compiler&linker
template<>
void QuickSort<int>(vector<int> &array) {
	QuickSortBody(array, 0, array.size() - 1);
}

template<>
void QuickSort<ConvexHullPoint>(vector<ConvexHullPoint> &points) {
	QuickSortBody(points, 0, points.size() - 1);
}

template<class T>
void Partition(vector<T> &array, int begin, int &mid, int end);
template<class T>
void QuickSortBody(vector<T> &array, int begin, int end) {
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	Partition(array, begin, mid, end);

	QuickSortBody(array, begin, mid - 1);
	QuickSortBody(array, mid + 1, end);
}

template<class T>
void Partition(vector<T> &array, int begin, int &mid, int end) {
	int pos = begin, i = pos + 1;
	swap(array[mid], array[begin]);
	while (i <= end) {
		if (array[pos + 1] <= array[begin]) {
			++pos;
			++i;
		}
		else {
			for (; i <= end; ++i) {
				if (array[i] <= array[begin]) {
					swap(array[i], array[pos + 1]);
					++pos;
					break;
				}
			}
		}	
	}
	mid = pos;
	swap(array[begin], array[pos]);

#if 0
	cout<<endl;
	copy(array.begin(), array.end(), ostream_iterator<int>(cout, " "));
	cout<<endl;
#endif
}

int BinarySearchBody(const vector<int> &array, int begin, int end, int ele);
int BinarySearch(const vector<int> &array, int ele) {
	return BinarySearchBody(array, 0, array.size() - 1, ele);
}

int BinarySearchBody(const vector<int> &array, int begin, int end, int ele) {
	if (begin > end)
		return -1;

	int mid = (begin + end) / 2;

	if (ele == array[mid])
		return mid;
	else if (ele < array[mid]){
		return BinarySearchBody(array, begin, mid - 1, ele);
	} else
		return BinarySearchBody(array, mid + 1, end, ele);
}

void PreorderTraversal(BinaryTree *root) {
	if (!root)
		return;

	cout<<root->data<<" ";
	PreorderTraversal(root->leftchild);
	PreorderTraversal(root->rightchild);
}

void InorderTraversal(BinaryTree *root) {
	if (!root)
		return;

	InorderTraversal(root->leftchild);
	cout<<root->data<<" ";
	InorderTraversal(root->rightchild);
}

void PostorderTraversal(BinaryTree *root) {
	if (!root)
		return;

	PostorderTraversal(root->leftchild);
	PostorderTraversal(root->rightchild);
	cout<<root->data<<" ";
}

int BinaryTreeHeight(BinaryTree *root) {
	if (!root)
		return 0;

	return max(BinaryTreeHeight(root->leftchild) + 1, 
			BinaryTreeHeight(root->rightchild) + 1);
}

double SlopeFunction(const ConvexHullPoint &pt1, const ConvexHullPoint &pt2) {
	if (pt1.GetX() == pt2.GetX())
		return DOUBLE_MAX;

	return double(pt2.GetY() - pt1.GetY()) / (pt2.GetX() - pt1.GetX());
}

double DistanceFunction(const ConvexHullPoint &pt1, \
						const ConvexHullPoint &pt2, \
						const ConvexHullPoint &pt3) {
	//line: Ax + By + C = 0
	//distance: |(AXo + BYo + C) / sqrt(A^2 + B^2)|
	//y = kx + b we use this one
	double k = SlopeFunction(pt2, pt3);
	if (k == DOUBLE_MAX)
		return abs(pt2.GetX() - pt1.GetX());

	double b = pt2.GetY() - k * pt2.GetX();
	return abs(k * pt1.GetX() + b - pt1.GetY()) / sqrt(k * k + 1);
}

void ConvexHullSolution(const vector<ConvexHullPoint> &points, \
						vector<ConvexHullPoint> &result) {
	if (points.empty())
		return;
	if (points.size() == 1) {
		result.push_back(points.back());
		return;
	}
	if (points.size() == 2)
		return;

	vector<ConvexHullPoint> up, down;
	up.push_back(points.front());
	up.push_back(points.back());
	down = up;
	//not finished

}

void ShellPass(vector<int> &array, int step) {
	for (int i = step; i < array.size(); i += 1) {
		int temp = array[i];
		int j = i - step;
		for (; j >= 0; j -= step) {
			if (array[j] > temp)
				array[j + step] = array[j];
			else
				break;
		}
		array[j + step] = temp;
	}

#if 0
	cout<<endl;
	copy(array.begin(), array.end(), ostream_iterator<int>(cout, " "));
	cout<<endl;
#endif
}

void ShellSort(vector<int> &array) {
	int step = array.size();
	do {
		step /= 2;
		ShellPass(array, step);
	} while (step > 1);
}

vector<pair<LinkNode *, int> >::iterator VertexStatus(Graph *graph, LinkNode *vertex) {
	vector<pair<LinkNode *, int> >::iterator it = graph->graphlink.begin();
	vector<pair<LinkNode *, int> >::iterator notfound = graph->graphlink.end();

	for (; it != graph->graphlink.end(); ++it) {
		if (it->first->node == vertex->node)
			return it;
	}

	return notfound;
}

void DFSVertex(Graph *graph, LinkNode *vertex);
void DFS(Graph *graph) {
	vector<pair<LinkNode *, int> >::iterator it = graph->graphlink.begin();
	for (; it != graph->graphlink.end(); ++it) {
#if 0
		LinkNode *head = it->first;
		cout<<it->second<<" ";
		while (head) {
			cout<<head->node<<" ";
			head = head->next;
		}
		cout<<endl;
#else
		if (it->second == 0) {
			//cout<<"("<<it->first->node<<")"<<" "; 
			DFSVertex(graph, it->first);
		}
#endif
	}
}

void DFSVertex(Graph *graph, LinkNode *vertex) {
	vector<pair<LinkNode *,int> >::iterator status = VertexStatus(graph, vertex);
	cout<<vertex->node<<" ";
	status->second = 1;

#if 0
	vector<pair<LinkNode *, int> >::iterator it = graph->graphlink.begin();
	cout<<endl;
	for (; it != graph->graphlink.end(); ++it) {
		cout<<it->second<<" "<<it->first->node<<endl;
	}
#endif

	vertex = vertex->next;
	while (vertex) {
		//cout<<"["<<vertex->node<<"] ";
		status = VertexStatus(graph, vertex);
		if (status->second == 0) {
			vector<pair<LinkNode *, int> >::iterator graphvertex = VertexStatus(graph, vertex);
			DFSVertex(graph, graphvertex->first);
		}
		vertex = vertex->next;
	}
}

void BFSVertex(Graph *graph, LinkNode *vertex);
void BFS(Graph *graph) {
	vector<pair<LinkNode *, int> >::iterator it;
	it = graph->graphlink.begin();
	for (; it != graph->graphlink.end(); ++it) {
#if 0
		LinkNode *head = it->first;
		cout<<it->second<<" ";
		while (head) {
			cout<<head->node<<" ";
			head = head->next;
		}
		cout<<endl;
#else
		if (it->second == 0)
			BFSVertex(graph, it->first);
#endif
	}
}

void BFSVertex(Graph *graph, LinkNode *vertex) {
	queue<LinkNode *> quevertex;
	vector<pair<LinkNode *, int> >::iterator graphvertex;
	quevertex.push(vertex);
	while (!quevertex.empty()) {
		LinkNode *front = quevertex.front();
		for (front = front->next; front; front = front->next) {
			graphvertex = VertexStatus(graph, front);
			if (graphvertex->second == 0)
				quevertex.push(graphvertex->first);
		}
		graphvertex = VertexStatus(graph, quevertex.front());
		if (graphvertex->second == 0) {
			graphvertex->second = 1;
			cout<<graphvertex->first->node<<" ";
		}
		quevertex.pop();
	}
}
